class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []
        def dfs(i):
            d = k - len(path) # 还要选 d 个数
            if d == 0:
                ans.append(path.copy())
                return
            for c in range(i, d - 1, -1): # 枚举的数不能太小，否则后面没有数可以选
                path.append(c)
                dfs(c - 1)
                path.pop()   # 恢复现场
        dfs(n)
        return ans